public class No055 {
    /**
     * 输入一棵二叉树，求该树的深度。
     * 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
     */
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        return TreeDepthCore(root);
    }

    public int TreeDepthCore(TreeNode root) {
        if (root == null) return 0;
        int leftCount = TreeDepthCore(root.left);
        int rightCount = TreeDepthCore(root.right);
        return Math.max(leftCount, rightCount) + 1;
    }

    /**
     * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
     */
    public int TreeDepthCore2(TreeNode root) {
        if (root == null) return 0;
        int leftCount = TreeDepthCore2(root.left);
        if (leftCount == -1) return -1; //如果发现子树不平衡之后就没有必要进行下面的高度的求解了
        int rightCount = TreeDepthCore2(root.right);
        if (rightCount == -1) return -1;//如果发现子树不平衡之后就没有必要进行下面的高度的求解了
        if (Math.abs(leftCount - rightCount) > 1)
            return -1;
        else
            return 1 + (Math.max(leftCount, rightCount));
    }

    public boolean IsBalanced_Solution(TreeNode root) {
        return TreeDepthCore2(root) != -1;
    }
}
